1. Field of the Invention
This invention relates generally to digital signal processing, and in particular to methods for carrying out an inverse Fast Fourier Transform.
2. Description of the Related Art
Quantization noise in an Inverse Fast Fourier Transform (IFFT) used, for example, in digital signal processing (DSP), can result in an output that contains errors having relatively large spectral peaks, when analyzed in the spectral domain. Such quantization noise in the IFFT used in DSP is especially noticeable for low-level signals. For example, for audio signals, the quantization noise can result in an audible tonal noise that can be objectionable.
Typically, the IFFT used in DSP is performed using the same data type throughout, for example, B-bit data. When the IFFT used in DSP is implemented using either dedicated digital signal processors or general purpose digital computer processors with a finite word length, quantization noise will appear in the output. If the quantization noise is too large, typical corrective actions include: 1) increasing the word length or size, for example, to accommodate 2B-bit data, thus reducing the quantization error and/or 2) using floating-point representations instead of using fixed point representations. However, increasing word length and/or using floating-point representations can significantly increase circuit size and complexity and/or program execution time and/or required data storage.
The Fast Fourier Transform (FFT) is a well known algorithm used in DSP for transforming a set of N time-domain sample points into a corresponding set of N frequency-domain sample points. The FFT processes find utility in a variety of applications, including machine-implemented speech recognition, image enhancement or video or tomography signals, adaptive filtering of digitized waveforms, audio compression and so forth.
The basic FFT equations are: ##EQU1##
where j=.sqroot.(-1) so that j.sup.2 =-1, j.sup.3 =-j and j.sup.4 =+1. The time-domain samples are represented as x(0) through x(N-1). The frequency-domain samples are represented as X(0) through X(N-1).
The basic FFT equations show that each frequency-domain component X(p) is a weighted sum of all N time-domain components x(n), for n=0, 1, 2, . . . , N-1. The weights W.sub.N.sup.np are referred to as twiddle factors.
The basic IFFT equations are: ##EQU2## where z*=x-jy is the complex conjugate of z=x+jy. The basic IFFT equations show that each time-domain component x(n) is a weighted average of all N frequency-domain components X(p), for p=0, 1, 2, . . . , N-1. The weights W.sub.N.sup.-np =[W.sub.N.sup.np ]* for the IFFT are the complex conjugates of the twiddle factors W.sub.N.sup.np for the FFT. The expression in the brackets in the second equation for each time-domain component x(n) is recognizable as the FFT of the sequence {X*(p)}(for p=0, 1, 2, . . . , N-1), the complex conjugate of the frequency-domain component sequence {X(p)}(for p=0, 1, 2, . . . , N-1). Thus, the IFFT for each time-domain component x(n) can be computed by taking the complex conjugate of the FFT of the sequence {X*(p)}(for p=0, 1, 2, . . . , N-1), and dividing by the number of points N.
The basic FFT equation ##EQU3## for p=0, 1, 2, . . . , N-1, can be inserted into the basic IFFT equation ##EQU4## for n=0, 1, 2, . . . , N-1, to give: ##EQU5##
where ##EQU6## where .delta..sub.kn is the Kronecker delta.
Similarly, the basic IFFT equation ##EQU7## for n=0, 1, 2, . . . , N-1, can be inserted into the basic FFT equation ##EQU8## for p=0, 1, 2, . . . , N-1, to give: ##EQU9## Thus, the FFT and IFFT are, indeed, an invertible transform pair.
Machine-implemented computation of an FFT is often simplified by cascading together a series of simple multiply-and-add sections. When a recursive process is used, data circulates through a single section and the computational structure of the section is made variable for each circulation. Each circulation through the section is referred to as a "pass". When the number N of time-domain and frequency-domain sample points satisfies the relation N=2.sup.M, where M is a positive integer, then the number M is typically referred to as the number of "stages" of the FFT.
A plurality of computational elements, each known as a radix-r butterfly, may be assembled to define a single section of the FFT for carrying out a particular pass. A radix-r butterfly receives r input signals and produces a corresponding number of r output signals, where each output signal is the weighted sum of the r input signals. The radix number, r, in essence, defines the number of input components that contribute to each output component.
By way of example, as shown in FIG. 1, a radix-2 butterfly for a decimation-in-time (DIT) FFT receives two input signals A and B and produces two output signals X and Y so that X=A+W.sub.N.sup.k B and Y=A-W.sub.N.sup.k B, where ##EQU10## and the k on the arrow heading into the open circle shown in FIG. 1 represents the exponent of the twiddle factor W.sub.N.sup.k. Each output signal X=A+W.sub.N.sup.k B and Y=A-W.sub.N.sup.k B is the weighted sum of the two input signals A and B.
As shown in FIG. 2, a radix-4 butterfly for a DIT FFT receives four input signals A, B, C and D and produces four output signals X, Y, Z and V so that X=A+W.sub.N.sup.k B+W.sub.N.sup.l C+W.sub.N.sup.m D, Y=A-jW.sub.N.sup.k B-W.sub.N.sup.l C+jW.sub.N.sup.m D, Z=A-W.sub.N.sup.k B+W.sub.N.sup.l C-W.sub.N.sup.m D and V=A+jW.sub.N.sup.k B-W.sub.N.sup.l C-jW.sub.N.sup.m D, where ##EQU11## and the k, l
and m on the arrows heading into the open circle shown in FIG. 2 represent the exponents of the twiddle factors W.sub.N.sup.k, W.sub.N.sup.l and W.sub.N.sup.m. Each output signal X=A+W.sub.N.sup.k B+W.sub.N.sup.l C+W.sub.N.sup.m D, Y=A-jW.sub.N.sup.k B-W.sub.N.sup.l C+jW.sub.N.sup.m D, Z=A-W.sub.N.sup.k B+W.sub.N.sup.l C-W.sub.N.sup.m D and V=A+jW.sub.N.sup.k B-W.sub.N.sup.l C-jW.sub.N.sup.m D is the weighted sum of the four input signals A, B, C and D.
Completion of an N-point FFT requires that the product of the butterfly radix values, taken over the total number of sections or passes, equals the total point count, N. Thus, a 64-point FFT (constituting 6 stages since 64=2.sup.6) can be performed by one section (constituting all 6 stages at once) having 1 radix-64 butterfly or two cascaded sections (each constituting 3 stages) where each section has 8 radix-8 butterflies (the product of the radix values for section-1 and section-2 is 8.times.8=64) or three cascaded sections (each constituting 2 stages) where each section has 16 radix-4 butterflies (the product of the radix values for section-1, section-2 and section-3 is 4.times.4.times.4=64) or six cascaded sections (each constituting 1 stage) where each section (or stage) has 32 radix-2 butterflies (the product of the radix values for section-1 through section-6 is 2.times.2.times.2.times.2.times.2.times.2=64).
It has been shown that multi-section or multi-pass FFT processes can be correctly carried out under conditions where the number of butterfly elements changes from one pass or section to the next and the corresponding radix value r.sub.i (of the butterfly elements of section-i) also changes accordingly from one pass or section to the next. A mixed-radix system is one where the radix value r.sub.i (of the butterfly elements of section-i) is different from at least one radix value r.sub.k (of the butterfly elements of section-k) for i.noteq.k.
An advantage of a mixed-radix computing system is that it can be "tuned" to optimize the signal-to-noise ratio of the FFT and/or to minimize the accumulated round-off error of the total FFT for each particular set of circumstances. By way of example, it may be advantageous in one environment to perform a 64-point FFT using the mixed-radix sequence: 2, 4, 4, 2. In a different environment, it may be more advantageous to use the mixed-radix sequence: 4, 2, 4, 2. Round-off error varies within a machine of finite precision as a function of radix value and the peak signal magnitudes that develop in each section or pass.
The Cooley-Tukey algorithm, as described in E. Oran Brigham, The Fast Fourier Transform, Prentice-Hall, Englewood Cliffs, N.J., 1974, pp. 188-190, provides an N-point DIT FFT for arbitrary radix where N=r.sub.1 r.sub.2 . . . r.sub.m, where r.sub.1, r.sub.2, . . . , r.sub.m are all integer valued. Expressing the indices n and p in a variable radix representation: EQU p=p.sub.m-1 (r.sub.1 r.sub.2 . . . r.sub.m-1)+p.sub.m-2 (r.sub.1 r.sub.2 . . . r.sub.m-2)+ . . . +p.sub.2 r.sub.1 .sub.2 +p.sub.1 r.sub.1 +p.sub.0 EQU n=n.sub.m-1 (r.sub.2 r.sub.3 . . . r.sub.m)+n.sub.m-2 (r.sub.3 r.sub.4 . . . r.sub.m)+ . . . +n.sub.2 r.sub.m-1 r.sub.m +n.sub.1 r.sub.m +n.sub.0 where
p.sub.i-1 =0,1,2, . . . r.sub.i -1;1.ltoreq.i.ltoreq.m and n.sub.i =0,1,2, . . . , r.sub.m-i -1;0.ltoreq.i.ltoreq.m-1, the basic FFT equation ##EQU12## for p=0, 1, 2, . . . , N-1, becomes: ##EQU13## where the time-domain samples x(n) are presented in digit-reversed order so that the resulting frequency-domain samples X(p) will be in natural digit order. Since ##EQU14## using ##EQU15## for any integer s, then ##EQU16## where the brackets define the first section of the N-point DIT FFT: ##EQU17## Similarly, since ##EQU18##
again using ##EQU19## for any integer s, then ##EQU20## where the brackets define the second section of the N-point DIT FFT: ##EQU21## Generally the kth section of the N-point DIT FFT is defined, for 2.ltoreq.k.ltoreq.m-1, as follows: ##EQU22## so that, for example, the third section of the N-point DIT FFT is: ##EQU23## is the mth and final section of the N-point DIT FFT.
For example, the N-point DIT FFT for N=r.sub.1, where r.sub.1 is integer valued, becomes: ##EQU24## which, for r.sub.1 =2 is just the radix-2 butterfly for a DIT FFT, as shown in FIG. 1, with k=0, A=x(0), B=x(1), X=X(0) and Y=X(1). Similarly, for r.sub.1 =4, ##EQU25## is just the radix-4 butterfly for a DIT FFT, as shown in FIG. 2, with k=l=m=0, A=x(0), B=x(1), C=x(2), D=x(3), X=X(0), Y=X(1), Z=X(2) and V=X(3).
Likewise, the N-point DIT FFT for N=r.sub.1 r.sub.2, where r.sub.1 and r.sub.2 are integer valued, becomes: ##EQU26## which, for r.sub.1 =2=r.sub.2, is given by just two stages of 2 radix-2 butterflies each, as shown in FIG. 3. Expanded out, the 4-point DIT FFT, for N=2.sup.2, is given by:
X(00)=x.sub.2 (00)=x.sub.1 (00)+x.sub.1 (10)=[x(00)+x(10)]+[x(01)+x(11)],
X(01)=x.sub.2 (01)=x.sub.1 (01)+(W.sub.4).sup.1 x.sub.1 (11)=[x(00)-x(10)]+(W.sub.4).sup.1 [x(01)-x(11)],
X(10)=x.sub.2 (10)=x.sub.1 (00)-x.sub.1 (10)=[x(00)+x(10)]-[x(01)+x(11)],
X(11)=x.sub.2 (11)=x.sub.1 (01)-(W.sub.4).sup.1 x.sub.1 (11)=[x(00)-x(10)]-(W.sub.4).sup.1 [x(01)-x(11)], where the arguments of the time-domain samples x(n) and the frequency-domain samples X(p) are presented in binary form, n.sub.1 n.sub.0 and p.sub.1 p.sub.0. As shown in FIG. 3, the time-domain samples x(n) are input to the radix-2 first stage in (binary) digit-reversed order (reversed-binary order), {00,10,01,11}, while the frequency-domain samples X(p) are output from the final radix-2 stage (the second stage, in this example) in natural (binary) digit order, {00,01,10,11}. A correspondence with the radix-4 butterfly for a DIT FFT, as shown in FIG. 2, with k=l=m=0, may be made with the identifications: A=x(00), B=x(01), C=x(10), D=x(11), X=X(00), Y=X(01), Z=X(10) and V=X(11).
The N-point DIT FFT for N=r.sub.1 r.sub.2 r.sub.3, where r.sub.1, r.sub.2 and r.sub.3 are integer valued, becomes: ##EQU27## which, for r.sub.1 =2=r.sub.2 =r.sub.3 is given by three stages of 4 radix-2 butterflies each, as shown in FIG. 4. Expanded out, the 8-point DIT FFT, for N=2.sup.3, is given by:
X(000)=x.sub.3 (000)=x.sub.2 (000)+x.sub.2 (100)=[x.sub.1 (000)+x.sub.1 (010)]+[x.sub.1 (100)+x.sub.1 (110)]=[[x(000)+x(100)]+[x(010)+x(110)]]+[[x(001)+x(101)]+[x(011)+x(111)]]
X(001)=x.sub.3 (001)=x.sub.2 (001)+(W.sub.8).sup.1 x.sub.2 (101)=[x.sub.1 (001)-jx.sub.1 (011)]+(W.sub.8).sup.1 [x.sub.1 (101)-jx.sub.1 (111)]=[[x(000)-x(100)]-j[x(010)-x(110)]]+(W.sub.8).sup.1 [[x(001)-x(101)]-j[x(011)-x(111)]],
X(010)=x.sub.3 (010)=x.sub.2 (010)+(W.sub.8).sup.2 x.sub.2 (110)=[x.sub.1 (000)-x.sub.1 (010)]+(W.sub.8).sup.2 [x.sub.1 (100)-x.sub.1 (110)]=[[x(000)+x(100)]-[x(010)+x(110)]]+(W.sub.8).sup.2 [[x(001)+x(101)]-[x(011)+x(111)]],
X(011)=x.sub.3 (011)=x.sub.2 (011)+(W.sub.8).sup.3 x.sub.2 (111)=[x.sub.1 (001)+jx.sub.1 (011)]+(W.sub.8).sup.3 [x.sub.1 (101)+jx.sub.1 (111)]=[[x(000)-x(100)]+j[x(010)-x(110)]]+(W.sub.8).sup.3 [[x(001)-x(101)]+j[x(011)-x(111)]],
X(100)=x.sub.3 (100)=x.sub.2 (000)-x.sub.2 (100)=[x.sub.1 (000)+x.sub.1 (010)]-[x.sub.1 (100)+x.sub.1 (110)]=[[x(000)+x(100)]+[x(010)+x(110)]]-[[x(001)+x(101)]+[x(011)+x(111)]]
X(101)=x.sub.3 (101)=x.sub.2 (001)-(W.sub.8).sup.1 x.sub.2 (101)=[x.sub.1 (001)-jx.sub.1 (011)]-(W.sub.8).sup.1 [x.sub.1 (101)-jx.sub.1 (111)]=[[x(000)-x(100)]-j[x(010)-x(110)]]-(W.sub.8).sup.1 [[x(001)-x(101)]-j[x(011)-x(111)]],
X(110)=x.sub.3 (110)=x.sub.2 (010)-(W.sub.8).sup.2 x.sub.2 (110)=[x.sub.1 (000)-x.sub.1 (010)]-(W.sub.8).sup.2 [x.sub.1 (100)-x.sub.1 (110)]=[[x(000)+x(100)]-[x(010)+x(110)]]-(W.sub.8).sup.2 [[x(001)+x(101)]-[x(011)+x(111)]],
X(111)=x.sub.3 (111)=x.sub.2 (011)-(W.sub.8).sup.3 x.sub.2 (111)=[x.sub.1 (001)+jx.sub.1 (011)]-(W.sub.8).sup.3 [x.sub.1 (101)+jx.sub.1 (111)]=[[x(000)-x(100)]+j[x(010)-x(110)]]-(W.sub.8).sup.3 [[x(001)-x(101)]+j[x(011)-x(111)]],
where the arguments of the time-domain samples x(n) and the frequency-domain samples X(p) are presented in binary form, p.sub.2 p.sub.1 p.sub.0 and n.sub.2 n.sub.1 n.sub.0. As shown in FIG. 4, the time-domain samples x(n) are input to the radix-2 first stage in (binary) digit-reversed order (reversed-binary order), {000,100,010,110,001,101,011,111}, while the frequency-domain samples X(p) are output from the final radix-2 stage (the third stage, in this example) in natural (binary) digit order, {000,001,010,011,100,101,110,111}.
The 8-point DIT FFT for N=r.sub.1 r.sub.2, where r.sub.1 =2 and r.sub.2 =4, becomes: ##EQU28## which is given by a first section (one stage) of 4 radix-2 butterflies followed by a second section of 2 radix-4 butterflies, as shown in FIG. 5. Expanded, the 8-point DIT FFT, for N=r.sub.1 r.sub.2, where r.sub.1 =2 and r.sub.2 =4, is given by:
X(00)=x.sub.2 (00)=x.sub.1 (00)+x.sub.1 (10)+x.sub.1 (20)+x.sub.1 (30) =[x(00)+x(10)]+[x(01)+x(11)]+[x(02)+x(12)]+[x(03)+x(13)],
X(01)=x.sub.2 (01)=x.sub.1 (01)+(W.sub.8).sup.1 x.sub.1 (11)+(W.sub.8).sup.2 x.sub.1 (21)+(W.sub.8).sup.3 x.sub.1 (31) =[x(00)-x(10)]+(W.sub.8).sup.1 [x(01)-x(11)]+(W.sub.8).sup.2 [x(02)-x(12)]+(W.sub.8).sup.3 [x(03)-x(13)],
X(10)=x.sub.2 (10)=x.sub.1 (00)-jx.sub.1 (10)-x.sub.1 (20)+jx.sub.1 (30) =[x(00)+x(10)]-j[x(01)+x(11)]-[x(02)+x(12)]+j[x(03)+x(13)],
X(11)=x.sub.2 (11)=x.sub.1 (01)-j(W.sub.8).sup.1 x.sub.1 (11)-(W.sub.8).sup.2 x.sub.1 (21)+j(W.sub.8).sup.3 x.sub.1 (31) =[x(00)-x(10)]-j(W.sub.8).sup.1 [x(01)-x(11)]-(W.sub.8).sup.2 [x(02)-x(12)]+j(W.sub.8).sup.3 [x(03)-x(13)],
X(20)=x.sub.2 (20)=x.sub.1 (00)-x.sub.1 (10)+x.sub.1 (20)-x.sub.1 (30) =[x(00)+x(10)]-[x(01)+x(11)]+[x(02)+x(12)]-[x(03)+x(13)],
X(21)=x.sub.2 (21)=x.sub.1 (01)-(W.sub.8).sup.1 x.sub.1 (11)+(W.sub.8).sup.2 x.sub.1 (21)-(W.sub.8).sup.3 x.sub.1 (31) =[x(00)-x(10)]-(W.sub.8).sup.1 [x(01 )-x(11)]+(W.sub.8).sup.2 [x(02)-x(12)]-(W.sub.8).sup.3 [x(03)-x(13)],
X(30)=x.sub.2 (30)=x.sub.1 (00)+jx.sub.1 (10)-x.sub.1 (20)-jx.sub.1 (30) =[x(00)+x(10)]+j[x(01)+x(11)]-[x(02)+x(12)]-j[x(03)+x(13)],
X(31)=x.sub.2 (31)=x.sub.1 (01)+j(W.sub.8).sup.1 x.sub.1 (11)-(W.sub.8).sup.2 x.sub.1 (21)-j(W.sub.8).sup.3 x.sub.1 (31) =[x(00)-x(10)]+j(W.sub.8).sup.1 [x(01)-x(11)]-(W.sub.8).sup.2 [x(02)-x(12)]-j(W.sub.8).sup.3 [x(03)-x(13)], where the arguments of the time-domain samples x(n) are presented in binary/ternary form, n.sub.1 n.sub.0, with n=4n.sub.1 +n.sub.0, for n.sub.1 =0, 1, and n.sub.0 =0, 1, 2, 3, and the frequency-domain samples X(p) are presented in ternary/binary form, p.sub.1 p.sub.0, with p=2p.sub.1 +p.sub.0, for p.sub.1 =0, 1, 2, 3, and p.sub.0 =0, 1. As shown in FIG. 5, the time-domain samples x(n) are input to the radix-2 first section (first stage) in (ternary/binary) digit-reversed order, {00,10,01,11,02,12,03,13}, while the frequency-domain samples X(p) are output from the radix-4 second section in natural (ternary/binary) digit order, {00,01,10,11,20,21,30,31}. The (ternary/binary) digit-reversed order, {00,10,01,11,02,12,03,13}, may be obtained simply by reversing the order of the digits in the natural (ternary/binary) digit order, {00,01,10,11,20,21,30,31}.
Similarly, the 8-point DIT FFT for N=r.sub.1 r.sub.2, where r.sub.1 =4 and r.sub.2 =2, becomes: ##EQU29## which is given by a first section of 2 radix-4 butterflies followed by a second section of 4 radix-2 butterflies, as shown in FIG. 6. Expanded, the 8-point DIT FFT, for N=r.sub.1 r.sub.2, where r.sub.1 =4 and r.sub.2 =2, is given by:
X(00)=x.sub.2 (00)=x.sub.1 (00)+x.sub.1 (10) =[x(00)+x(10)+x(20)+x(30)]+[x(01)+x(11)+x(21)+x(31)],
X(01)=x.sub.2 (01)=x.sub.1 (01)+(W.sub.8).sup.1 x.sub.1 (11) =[x(00)-jx(10)-x(20)+jx(30)]+(W.sub.8).sup.1 [x(01)-jx(11)-x(21)+jx(31)],
X(02)=x.sub.2 (02)=x.sub.1 (02)+(W.sub.8).sup.2 x.sub.1 (12) =[x(00)-x(10)+x(20)-x(30)]+(W.sub.8).sup.2 [x(01)-x(11)+x(21)-x(31)],
X(03)=x.sub.2 (03)=x.sub.1 (03)+(W.sub.8).sup.3 x.sub.1 (13) =[x(00)+jx(10)-x(20)-jx(30)]+(W.sub.8).sup.3 [x(01)+jx(11)-x(21)-jx(31)],
X(10)=x.sub.2 (10)=x.sub.1 (00)-x.sub.1 (10) =[x(00)+x(10)+x(20)+x(30)]-[x(01)+x(11)+x(21)+x(31)],
X(11)=x.sub.2 (11)=x.sub.1 (01)-(W.sub.8).sup.1 x.sub.1 (11) =[x(00)-jx(10)-x(20)+jx(30)]-(W.sub.8).sup.1 [x(01)-jx(11)-x(21)+jx(31)],
X(12)=x.sub.2 (12)=x.sub.1 (02)-(W.sub.8).sup.2 x.sub.1 (12) =[x(00)-x(10)+x(20)-x(30)]-(W.sub.8).sup.2 [x(01)-x(11)+x(21)-x(31)],
X(13)=x.sub.2 (13)=x.sub.1 (03)-(W.sub.8).sup.3 x.sub.1 (13) =[x(00)+jx(10)-x(20)-jx(30)]-(W.sub.8).sup.3 [x(01)+jx(11)-x(21)-jx(31)], where the arguments of the time-domain samples x(n) are presented in ternary/binary form, n.sub.1 n.sub.0, with n=2n.sub.1 +n.sub.0, for n.sub.1 =0, 1, 2, 3, and n.sub.0 =0, 1, and the frequency-domain samples X(p) are presented in binary/ternary form, p.sub.1 p.sub.0, with p=4p.sub.1 +p.sub.0, for p.sub.1 =0, 1, and p.sub.0 =0, 1, 2, 3. As shown in FIG. 6, the time-domain samples x(n) are input to the radix-4 first section in (binary/ternary) digit-reversed order, {00,10,20,30,01,11,21,31}, while the frequency-domain samples X(p) are output from the radix-2 second section in natural (binary/ternary) digit order, {00,01,02,03,10,11,12,13}. The (binary/ternary) digit-reversed order, {00,10,20,30,01,11,21,31}, may be obtained simply by reversing the order of the digits in the natural (binary/ternary) digit order, {00,01,02,03,10,11,12,13}.
The foregoing examples suffice to demonstrate that the machine-implemented cascaded DIT FFT (and IFFT) may be readily generalized and extended to larger values for N, the number of sample points, as is well known in the art. Such large-N DIT FFTs and IFFTs are useful in digital signal processing (DSP) applications.
For example, a transform-based audio coding algorithm, such as Dolby.RTM. Digital, is designed to provide data-rate reduction for wide-band signals while maintaining the high quality of the original content, as described in L. Fielder et al. "AC-2 and AC-3: Low-Complexity Transform-Based Audio Coding," Collected Papers on Digital Audio Bit-Rate Reduction, Audio Engineering Society, New York, N.Y., pp. 54-72. Dolby.RTM. Digital is a high-quality audio compression format widely used in feature films and also with Digital Versatile Disks (DVDs), also known as Digital Video Disks. Many PC's offer DVD drives, and providing a Dolby.RTM. Digital decoder implemented in software, performing an IFFT as part of the implementation, allows decoding of Dolby.RTM. Digital to become a baseline capability on the PC.
Such a transform-based audio coding algorithm may be implemented on a PC based, for example, on an Intel Pentium.RTM. processor. It is important to maintain high audio quality, and Dolby.RTM. Laboratories has developed a stringent test suite to ensure that a certified decoder indeed provides high quality. In addition, trained listeners evaluate prospective decoders using both test and program material. Only after a decoder has passed both the analytical and subjective tests is the decoder certified.
An Intel Pentium.RTM. processor with Intel's MMX.TM. technology, for example, has MMX.TM. instructions that operate on 8, 16, and 32 bits. The human ear has an overall dynamic range of 120 dB and an instantaneous dynamic range of 85 dB, as described in S. Harris, "Understanding, enhancing, and measuring PC-audio quality," EDN, Vol. 42, Number 8, Apr. 10, 1997, p. 173. The dynamic range of a binary value is 6.0206 dB per bit. Eight bits (about 48 dB of dynamic range, approximately the dynamic range of AM radio) is not sufficient for high-quality audio. Sixteen bits (about 96 dB of dynamic range, the dynamic range of Compact Disks) is usually considered high-quality audio.
Due to quantization noise produced by rounding errors during the intermediate calculations, however, the accuracy at the output of a Dolby.RTM. Digital decoder, for example, is significantly less than the accuracy of the intermediate values (assuming a uniform accuracy throughout the transform-based audio coding algorithm). This is typical with DSP algorithms For example, using 16 bits of accuracy uniformly through a Dolby.RTM. Digital decoder is not sufficient to pass the Dolby.RTM. Laboratories test suite. The quantization noise produced using 16 bits of accuracy uniformly through a Dolby.RTM. Digital decoder, for example, can be both noticeable and tonal, making such an implementation unsatisfactory for high-quality audio. Tonal noise tends to be more objectionable than wideband or "white" noise.
The present invention is directed to overcoming, or at least reducing the effects of, one or more of the problems set forth above.